/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-08-18
 * Time: 11:20
 */
public class MyBinaryTree {
    public static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public int val;

        public TreeNode(int val){
            this.val=val;
        }
    }

    public TreeNode root;

    public void createBinaryTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }

    public void preOrder(TreeNode root){
        //根-》左-》右
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root){
        //左-》根-》右
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root){
        //左-》右-》根
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //获取树中节点个数
    public int size(TreeNode root){
        if(root==null){
            return 0;
        }
        //树的节点个数就是左子树的节点个数+右子树的节点个数+根节点
        return size(root.left)+size(root.right)+1;
    }

    //获取叶子结点的个数
    public int getLeafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    //获取第k层节点个数

    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);//k-1可以理解为k--
    }

    //求树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }

        int leftTree=getHeight(root.left);
        int rightTree=getHeight(root.right);

        return Math.max(leftTree,rightTree)+1;
        //每一个子树也要求到哪边是深一点的
    }

    //检测值为val的元素是否存在
    public TreeNode find(TreeNode root,int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }

        TreeNode leftTree=find(root.left,val);
        if(leftTree!=null){//如果左边找到了就直接从左边出去，不再参与右子树的递归了
            return leftTree;
        }

        TreeNode rightTree=find(root.right,val);
        if(rightTree!=null){
            return rightTree;
        }
        return null;
    }

    public boolean isSameTree(TreeNode p,TreeNode q) {
        //1.先检查是不是都为空，都为空的话就true
        if (p == null && q == null) {
             return true;
        }
        //2.如果一个为空，一个不为空，说明结构不相同
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        //3.判断完结构，就要判断数值是否相等
        if (p.val != q.val) {
            return false;
        }

        //假设我们上面比较的都只是根节点的，现在我们来比较左子树和右子树是否相等
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        //1.如果root等于null，那subRoot一定不可能是root的子树
        if(root==null){
            return false;
        }
        if(root==null&&subRoot==null){
            return true;
        }
        //2.很重要的一点：在还没有找到root.val和subRoot.val相等的这个节点时，只有root在遍历，subRoot没有动
        if(isSameTree(root,subRoot)){//检查subRoot是不是本身就跟root长得一摸一样
            return true;
        }
//        boolean leftTree=isSubTree(root.left,subRoot);
//        if(leftTree==true){
//            return true;
//        }
        if(isSubTree(root.left,subRoot)){
            return true;
        }
//        boolean rightTree=isSubTree(root.right,subRoot);
//        if(leftTree==true){
//            return true;
//        }
        if(isSubTree(root.right,subRoot)){
            return true;
        }

        return false;
    }

    public TreeNode invertTree(TreeNode root){
        if(root==null){
            return null;
        }
        if(root.left==null&&root.right==null){
            return root;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}
